/*
day75
2019.11.11
*/

#include<vector>
#include<stack>
#include<queue>
using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};


class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root) 
	{
	    vector<vector<int>> vec_res;
	    stack<struct TreeNode *> sta_left;
	    stack<struct TreeNode *> sta_right;
	    
		if(root) sta_right.push(root);
		struct TreeNode *cur;
		while(!sta_right.empty())
		{
			vector<int> vec1;
			while(!sta_right.empty())
			{
				cur=sta_right.top();
				vec1.push_back(cur->val);
				sta_right.pop();
				if(cur->left) sta_left.push(cur->left);
				if(cur->right) sta_left.push(cur->right);
			}
			if(!vec1.empty()) vec_res.push_back(vec1);
			
			vector<int> vec2;
			while(!sta_left.empty())
			{
				cur=sta_left.top();
				vec2.push_back(cur->val);
				sta_left.pop();
				if(cur->right) sta_right.push(cur->right);
				if(cur->left) sta_right.push(cur->left);
			}
			if(!vec2.empty()) vec_res.push_back(vec2);
		}
		return vec_res;
    }
};

 

int main()
{
	return 0;
}
